package string

//数组+回溯法
func longestPalindromeSubseq(s string) int {
	if len(s) <= 1 {
		return len(s)
	}
	counter := make([][]int, len(s))
	for i := 0; i < len(s); i++ {
		counter[i] = make([]int, len(s))
	}

	result := longestPalindromeSubseq0(s, counter, 0, len(s)-1)
	return result
}
func longestPalindromeSubseq0(s string, counter [][]int, left, right int) int {
	if left > right {
		return 0
	}
	if left == right {
		counter[left][right] = 1
		return 1
	}
	if counter[left][right] > 0 {
		return counter[left][right]
	}
	r := containFirstLetterSubPalindromeSubSeq(s, left, right)
	var result = 1
	if r > left {
		result = 2 + longestPalindromeSubseq0(s, counter, left+1, r-1)
	}
	if result >= right-left {
		counter[left][right] = result
		return result
	}
	//不包含s[0]
	cnt := longestPalindromeSubseq0(s, counter, left+1, right)
	if cnt > result {
		result = cnt
	}
	counter[left][right] = result
	return result
}

//从右边开始数，和s[left]相同的字符位置。
func containFirstLetterSubPalindromeSubSeq(s string, left, right int) int {
	// i > 0， 看s是否包含了s[0]
	for i := right; i > left; i-- {
		if s[left] == s[i] {
			return i
		}
	}
	return left
}
